package Structure.MyLinkedList;

import java.util.Iterator;

/**
 * @author wang'ji'cheng
 * @date 2025/8/3
 */
public class DoubleLinkedList implements Iterable<Object> {

    //头哨兵
    private Node head;
    //尾哨兵
    private Node tail;
    //链表大小
    private int size;

    public DoubleLinkedList() {
        head = new Node(null, null, 0);
        tail = new Node(null, null, 0);
        //先头尾相连
        head.next = tail;
        tail.prev = head;
        size = 0;
    }



    static class Node {
        //上一个指针
        Node prev;
        //下一个指针
        Node next;
        //值
        Object value;


        public Node(Node prev, Node next, Object value) {
            this.prev = prev;
            this.next = next;
            this.value = value;
        }

    }

    private Node findNode(int index) {
        int i = -1;
        //一直循环遍历，什么时候，指针走到了为哨兵p==tail，循环结束
        for (Node p = head; p != tail; p = p.next, i++) {

            if (i == index) {
                return p;
            }

        }
        return null;
    }

    //添加节点
    public void insert(int index, Object value) {
        //添加位置的前一个节点
        Node prev = findNode(index - 1);
        if (prev == null) {
            throw new IndexOutOfBoundsException("索引越界");
        }
        //添加位置的节点
        Node next = prev.next;
        //要添加的节点
        Node node = new Node(prev, next, value);
        //前一个节点的后指针指向新节点
        prev.next = node;
        //后一个节点（原位置的节点）的前指针指向新节点
        next.prev = node;
    }

    public void delete(int index, Object value) {
        //找到删除位置的前一个节点
        Node prev = findNode(index - 1);
        if (prev == null) {
            throw new IndexOutOfBoundsException("索引越界");
        }
        //要删除的节点
        Node curr = prev.next;
        if (curr == tail) {
            throw new IndexOutOfBoundsException("索引越界");
        }
        Node next = curr.next;
        //前一个节点的后指针指向当前节点的下一个节点
        prev.next = next;
        //后一个节点的前指针指向当前节点的上一个节点
        next.prev = prev;
    }

    public void addLast(Object value) {
        //先找到最后一个节点
        Node prev = tail.prev;
        //创建新节点，前指针指向前一个，后指针指向尾哨兵
        Node node = new Node(prev, tail, value);
        //尾哨兵的前指针指向新添加的节点
        tail.prev = node;
        //前节点的后指针指向新节点
        prev.next = node;
    }

    public void deleteLast() {
        Node curr = tail.prev;
        if(curr==head){
            throw new  IndexOutOfBoundsException("索引不正确");
        }
        Node prev = curr.prev;
        prev.next = tail;
        tail.prev = prev;
    }

    @Override
    public Iterator<Object> iterator() {
        return new Iterator<Object>() {
            //设置起始位置
           Node p = head.next;
            @Override
            public boolean hasNext() {

                return p!=tail;
            }

            @Override
            public Object next() {
                Object value = p.value;
                 p = p.next;
                return value;
            }
        };

    }
}
